Baby-Step, Giant-Step

Baby-Step, Giant-Step is an algorithm for computing the discrete logarithm in a given group.

The problem statement, that we are trying to solve, is the following. Given \(g, a \in G\) for some finite group \(G\), where \(g\) is a generator for \(G\), find the \(x \in \mathbb{Z}\) with \(0 \leq x < |G|\) such that:

Which is to say, we are evaluating \(\log_g(a)\).

Motivation, and Description of Method

Naively, one might consider calculating powers of the primitive root \(g\) until the output \(a\) has been found. Baby-Step, Giant-Step begins with this, however we only calculate roots up to and not including \(\lceil \sqrt{n} \rceil\). These calculations are the baby steps from the name of the algorithm.

If we happen to find \(a\) already, then we are done, however this is unlikely.

Consider all consecutive powers of the primitive root listed in order as in the diagram below:

These are organised into sets of size \(\lceil \sqrt{n} \rceil\) and there are \(\lceil \sqrt{n} \rceil\) such sets, which means we have \(\lceil \sqrt{n} \rceil\lceil \sqrt{n} \rceil \geq n\) total powers, so there may be some overlap at the end.

Set \(0\) corresponds with the initial powers we calculated in the baby steps. Then, we compute \(g^{- \lceil \sqrt{n} \rceil}\).

We now take the giant steps. Consider that \(a\) is at the shaded pink circle below in set \(3\). In that case, \(g^{-\lceil \sqrt{n} \rceil} a\) puts it in set \(2\). In general, this shifts an element from set \(k\) to set \(k - 1\) (except of course at set \(0\)). After this multiplication, we check if it's in the pre-calculated set \(0\), if not, we repeat until it is.

Once it is, we know at that point that \(a\) multiplied by some power of \(g^{- \lceil \sqrt{n} \rceil}\) (where the power is given by the number of giant steps we took) is another known power of \(g\). This then makes it easy to solve for \(a\). Specifically, if \(i\) is the number of giant steps, and \(j\) is the corresponding power in set \(0\):

First note that in this case our group is of order \(16\). As such we need to compute the first \(\lceil \sqrt{15} \rceil\) following powers as follows:

Since we did not find \(17\), we now need to take our desired result of \(12\) and multiply by \(5^{-4}\). The best way to compute this depends on our group, in this case we can solve

using the extended euclidean algorithm, where \(5^4 = 5 \cdot 5^3\), the latter of which we have already computed.

This results in \(h = 5^{-4} = 4\).

We then have

Since we know that \(5 = 5^1\) (i.e. it appears on our first list of powers), we have that

Implementation

Here is an implementation of the algorithm in the specific case where the underlying group is the group of units modulo \(n\).

fn main() {
    println!("{}", baby_step_giant_step(13, 2, 3));
}

fn modular_exponent(base : u64, power : u64, modulus : u64) -> u64 {
    let mut result = 1;
    for _ in 0..power {
        result *= base % modulus;
    }

    result % modulus
}

/// We must have that:
/// - `modulus` is `prime`
/// - primitive_root is actually a primitive_root modulo `modulus`
/// - `logarithm` is some positive integer
/// This then computers `power` such that:
/// `primitive_root`^`power` = `logarithm` (mod `modulus`)
fn baby_step_giant_step(modulus : u64, primitive_root : u64, logarithm : u64) -> u64 {
    // Since modulus is prime, phi(modulus) = modulus - 1
    let group_order = modulus - 1;

    let m = (group_order as f64).sqrt() as u64 + 1;

    // Compute initial powers of the primitive_root (up to floor(sqrt(group_order)))
    let powers = {
        let mut powers = std::collections::HashMap::with_capacity(m as usize);

        let mut power = 1;
        for j in 0..m {
            powers.insert(power, j);
            power *= primitive_root % modulus;
        }

        powers
    };

    let mut guess = logarithm % modulus;
    for i in 0..m {
        match powers.get(&guess) {
            Some(power) => {
                return i * m + power;
            },
            None => {
                guess = (guess * modular_exponent(primitive_root, group_order - m, modulus)) % modulus;
            },
        }
    }

    unreachable!()
}